package offerbook;

import utils.TreeNode;
import utils.TreeUtil;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 序列化和反序列化树结构。
 * 如测试系统中关于二叉树的题目，后台答案就是把我们的答案序列化成字符串，然后对比
 * 序列化方式1： 按照遍历的方式序列化，有三种。怎么序列化就怎么反序列化
 */
public class Code62_SerializeAndReconstructTree {

    /*********采用先序遍历************/

    // Encodes a tree to a single string.
    public String serialize1(TreeNode root) {
        if (root == null) return "#_";
        String str = root.val + "_";
        str += serialize1(root.left);
        str += serialize1(root.right);
        return str;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize1(String data) {
        String[] splits = data.split("_");
        Queue<String> queue = new LinkedList<>(Arrays.asList(splits));
        return construct(queue);
    }

    //先序遍历还原，用队列还原数据。
    private TreeNode construct(Queue<String> queue) {
        String str = queue.poll();
        if ("#".equals(str)) return null;
        TreeNode TreeNode = new TreeNode(Integer.valueOf(str));
        TreeNode.left = construct(queue);
        TreeNode.right = construct(queue);
        return TreeNode;
    }

    /**********层次遍历************/
    // Encodes a tree to a single string.
    public static String serialize(TreeNode root) {
        if (root == null) return "#_";
        StringBuffer sb = new StringBuffer();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        sb.append(root.val).append("_");
        while (!queue.isEmpty()) {
            root = queue.poll();
            if (root.left != null) {
                sb.append(root.left.val).append("_");
                queue.offer(root.left);
            } else {
                sb.append("#_");
            }
            if (root.right != null) {
                sb.append(root.right.val).append("_");
                queue.offer(root.right);
            } else {
                sb.append("#_");
            }
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public static TreeNode deserialize(String data) {
        String[] splits = data.split("_");
        Queue<TreeNode> queue = new LinkedList<>();
        int index = 0;
        TreeNode root = generateNodeByString(splits[index++]);
        TreeNode head = root;
        if(head == null)return head;
        queue.offer(root);
        while (!queue.isEmpty()) {
            root = queue.poll();
            root.left = generateNodeByString(splits[index++]);
            root.right = generateNodeByString(splits[index++]);
            if (root.left != null) {
                queue.offer(root.left);
            }
            if (root.right != null) {
                queue.offer(root.right);
            }

        }
        return head;
    }

    private static TreeNode generateNodeByString(String val) {
        if (val.equals("#")) {
            return null;
        }
        return new TreeNode(Integer.valueOf(val));
    }

    public static void main(String[] args) {
        TreeNode head = null;
        TreeUtil.printTree(head);

        String pre = serialize(head);
        System.out.println("serialize tree by pre-order: " + pre);
        head = deserialize(pre);
        System.out.print("reconstruct tree by pre-order, ");
        TreeUtil.printTree(head);


        System.out.println("====================================");
        head = new TreeNode(1);
        head.left = new TreeNode(2);
        head.right = new TreeNode(3);
        head.left.left = new TreeNode(4);
        head.right.right = new TreeNode(5);
        TreeUtil.printTree(head);

        pre = serialize(head);
        System.out.println("serialize tree by pre-order: " + pre);
        head = deserialize(pre);
        System.out.print("reconstruct tree by pre-order, ");
        TreeUtil.printTree(head);

        System.out.println("abc".indexOf("b"));
    }
}
